TNotes.leetcode

Appearance

0897. 递增顺序搜索树【简单】

0897. 递增顺序搜索树【简单】 ​

1. 📝 题目描述 ​

给你一棵二叉搜索树的 root，请你按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

img

txt
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：

img

txt
输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

  • 树中节点数的取值范围是 [1, 100]
  • 0 <= Node.val <= 1000

2. 🎯 s.1 - 中序遍历 + 重建（伪头结点） ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function (root) {
  const dummy = new TreeNode(0)
  let cur = dummy

  const dfs = (node) => {
    if (!node) return
    dfs(node.left)
    // 根据目标节点更新当前节点
    cur.right = node // 将目标节点接到当前节点尾部（右侧）
    node.left = null // 断开目标节点的左指针
    cur = node // 当前节点下沉一层
    dfs(node.right)
  }

  dfs(root)
  return dummy.right
}
  • 时间复杂度：O(n)，中序遍历每个节点一次并重连
  • 空间复杂度：O(h)，递归栈深度，h 为树高

算法思路：

  • 对 BST 做中序遍历，访问顺序天然递增
  • 维护一个伪头结点 dummy 与尾指针 cur，每访问一个节点就接到 cur.right
  • 同时将当前节点的 left 置为 null，保证新树只有右子节点
  • 遍历结束返回 dummy.right 即为递增顺序搜索树

Discussions